public class JZ36 {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        TreeNode leftHead = Convert(pRootOfTree.left);
        TreeNode letfTail = leftHead;
        while (letfTail != null && letfTail.right != null){
            letfTail = letfTail.right;
        }
        if(letfTail != null){
            letfTail.right = pRootOfTree;
            pRootOfTree.left = letfTail;
        }
        TreeNode rightHead = Convert(pRootOfTree.right);
        if(rightHead != null){
            pRootOfTree.right = rightHead;
            rightHead.left = pRootOfTree;
        }
        return leftHead == null? pRootOfTree : leftHead;
    }
}
